package LC.nums.binarySearch;

public class LC69 {
    public static void main(String[] args) {
        int x = 9;
        System.out.println(mySqrt(x));
        System.out.println(binarySearch(x));
        System.out.println(mySqrtSimple(x));
    }

    public static int mySqrt(int x) {
        if (x == 1) {
            return 1;
        }
        int min = 0, max = x;
        while (max - min > 1) {
            int mid = (max + min) / 2;
            //用x/m<m而不是m*m>x防止溢出
            if (x / mid < mid)
                max = mid;
            else
                min = mid;
        }
        return min;
    }

    public static int binarySearch(int x) {
        int min = 0, max = x / 2 + 1;
        while (min <= max) {
            int mid = min + ((max - min) / 2);
            long sq = mid * mid;
            if (sq == x) return mid;
            else if (sq < x) min = mid + 1;
            else max = mid - 1;
        }
        return max;
    }

    public static int mySqrtSimple(int x) {
        if (x == 0) return 0;
        int last = 0, res = 1;
        while (res != last) {
            last = res;
            res = (res + x / res) / 2;
        }
        return res;
    }
}
